package com.hyb.algorithm.data.struct.sort;

/**
 * @Author: huyanbing
 * @Date: 2021/9/13 6:55 下午
 */
public class MergeSort {


    /**
     * Merge Sort 是一个O(nlogn)复杂度的算法，可以在1秒内轻松处理100万数量级别的数据
     * 不要轻易尝试使用SelectionSort InsertionSort 或者 BubbuleSort 处理100万级的数据
     * 否则你就见识了O(n^2)的算法和 O(nlogn)算法的本质差异
     *
     * @param arr
     */
    public static void sort(Comparable[] arr) {
        mergeSort(arr, 0, arr.length - 1);
    }

    //将arr[l....mid]和arr[mid+1...r] 两部分进行归并
    private static void mergeSort(Comparable[] arr, int left, int right) {

        if (left > right) {
            return;
        }

        int mid = left + (right - left) / 2;

        mergeSort(arr, left, mid);
        mergeSort(arr, mid, right);

        //对于arr[mid]<=arr[mid+1]的情况，不进行merge
        //对于近乎有序的数组非常有效，但是对于一般情况 有一定的性能损失
        if (arr[mid].compareTo(arr[mid + 1]) < 0) {
            return;
        }

        merge(arr, left, right, mid);

    }

    private static void merge(Comparable[] arr, int left, int right, int mid) {

        if (left >= right) {
            return;
        }

        int tempLength = right - left + 1;

        Comparable[] tempArr = new Comparable[tempLength];

        for (int i = left; i <= right; i++) {
            tempArr[i - left] = arr[i];
        }

        int leftP = left;
        int rightP = mid + 1;
        //初始化,i指向左半部分的起始索引位置l;j指向右半部分起始索引位置mid+1;
        for (int k = left; k <= right; k++) {
            //如果左半部分元素已经全部处理完毕
            if (leftP > mid) {
                arr[k] = tempArr[rightP - left];
                rightP++;
                continue;
            }

            //如果右半部分元素已经全部处理完毕
            if (rightP > right) {
                arr[k] = tempArr[leftP - left];
                leftP++;
                continue;
            }

            //左半部分所指元素<右半部分所指元素
            if (tempArr[leftP - left].compareTo(tempArr[rightP - left]) < 0) {
                arr[k] = tempArr[leftP - left];
                leftP++;
                continue;
            }

            //左半部分所指元素>=右半部分所指元素
            arr[k] = tempArr[rightP - left];
            rightP++;
            continue;


        }

    }

}
